package com.itheima.leetcode;

/**
 * 判断回文链表
 *
 * @FileName E09LeetCode234
 * @Description
 * @Author Sword
 * @date 2025-04-24
 **/
public class E09LeetCode234 {

    /*
        步骤1：找中间点的同时反转前半个链表
        步骤2：反转后的前半个链表 与 中间点开始的后半个链表 逐一比较

                p1      p2
        1   2   2   1   null

        n1
        2   1
     */
    public static boolean isPalindrome(ListNode head) {
        ListNode p1 = head;//慢
        ListNode p2 = head;//快
        ListNode n1 = null;//新头
        ListNode o1 = head;//旧头

        while (p2 != null && p2.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;

            //反转链表
//            ListNode o2 = o1.next;
            o1.next = n1;
            n1 = o1;
            o1 = p1;
        }

        System.out.println("n1" + n1);
        System.out.println("p1" + p1);


        if (p2 != null){    //奇数
            p1 = p1.next;
        }

        while (n1 != null) {
            if (n1.val != p1.val) {
                return false;
            }

            n1 = n1.next;
            p1 = p1.next;
        }

        /*ListNode middle = p1;

        System.out.println(middle);

        ListNode o1 = middle;
        ListNode n1 = null;

        while (o1 != null) {
            ListNode o2 = o1.next;
            o1.next = n1;
            n1 = o1;
            o1 = o2;
        }
        ListNode reverse = n1;

        System.out.println(reverse);
        System.out.println(head);

        while (reverse != null) {
            if (reverse.val != head.val) {
                return false;
            }

            head = head.next;
            reverse = reverse.next;
        }*/

        return true;
    }

    /*
        1   2   2   1

     */

    /*
        步骤1：找中间点
        步骤2：中间点后半个链表反转
        步骤3：反转后链表与原链表逐一比较
     */

    /*private static ListNode middle(ListNode head) {
        ListNode p1 = head;//慢
        ListNode p2 = head;//快

        while (p2 != null && p2.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
        }

        return p1;
    }

    private static ListNode reverse(ListNode o1) {
        ListNode n1 = null;

        while (o1 != null) {
            ListNode o2 = o1.next;
            o1.next = n1;
            n1 = o1;
            o1 = o2;
        }
        return n1;
    }*/

    public static void main(String[] args) {
        ListNode head = ListNode.of(1, 2, 2, 1);
        System.out.println(isPalindrome(head));

        /*ListNode head = ListNode.of(1, 2, 3, 2, 1);
        System.out.println(isPalindrome(head));*/

        /*
                    p1
                    o1
                            p2
            1   2   3   2   1   null

            n1
            2   1

            o1
            3   2   1
         */
    }
}
